﻿package list;

import common.Node;

/**
 * 一个环形单链表从头结点head开始不降序，同事由最后的节点指回头结点<br/>
 * 给定这样的一个环形单链表的头结点head和一个整数<br/>
 * num,请生成节点值为num的新节点，并插入到这个环形链表中， 保证调整后的链表依然有序<br/>
 */
public class 向有序的环形单节点中插入新结点 {
	public static Node addNewNode(Node head, int num) {
		Node node = new Node(num);
		if (head == null) {
			node.next = node;// 环形的链表
			return node;
		}
		// 如果head不为空
		Node cur = head;
		Node next = cur.next;
		while (cur != null) {
			if (cur.value < num && next.value > num) {
				// 找到了这个位置
				break;
			}
			cur = next;
			next = cur.next;
		}
		cur.next = node;
		node.next = next;
		return head;
	}
}
